﻿#include"Sort.h"
#include"stack.h"

//插入排序
//1)直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			//升序:>   降序:<
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

//2)希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while(gap>1)
	{ 
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			
			while (end >= 0)
			{
				//升序:>   降序:<
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


//选择排序
//1)直接选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = end;//这里从end开始的话后面的i就不再能从begin+1开始了
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		if (begin == maxi)
		{
			maxi = mini;
		}
		swap(&arr[begin], &arr[mini]);
		swap(&arr[end], &arr[maxi]);

		++begin;
		--end;
	}
}


//向下调整算法--O(logn)
void AdjustDown(int* arr, int parent, int n)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}
	}
}

//2)堆排序--nlogn
void HeapSort(int* arr, int n)
{
	//向下调整建堆,升序建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}



//交换排序
//1)冒泡排序
void BubbleSort(int* arr, int n)
{
	int exchange = 1;
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j+1])
			{
				swap(&arr[j], &arr[j+1]);
				exchange = 0;
			}
		}
		if (exchange == 1)
		{
			break;
		}
	}
}

//找基准
//1.hoare版本
int _QuickSort1(int* arr, int left, int right)
{
	int keyi = left;
	left++;
	//升序
	while (left <= right)
	{	
		//right从右往左找小,right必须大于等于left
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;
		}
		//left从左往右找大,right必须大于等于left
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		//交换左右,right必须大于等于left,交换完left后置++,right后置--
		if (left <= right)
		{
			swap(&arr[left++], &arr[right--]);
		}
	}
	//此时right所在位置就是基准位置
	swap(&arr[keyi], &arr[right]);
	return right;//返回right下标
}

//2.挖坑法
int _QuickSort2(int* arr, int left, int right)
{
	int hole = left;
	int key = arr[hole];
	while (left < right)
	{
		//right从右往左找小
		while (left<right && arr[right]> key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;

		//left从左往右找大
		while (left < right && arr[left] < key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}

//3.前后指针法
int _QuickSort3(int* arr, int left, int right)
{
	int prev = left;
	int cur = prev + 1;
	int keyi = left;

	while (cur <= right)
	{
		//从左往右找小，找到了就++prev(且！=cur)的话，就交换
		if (arr[cur] < arr[keyi]&&++prev!=cur)
		{
			swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	swap(&arr[keyi], &arr[prev]);
	return prev;
}


//2)快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return ;
	}
	//随机数取法
	//srand((unsigned int)time(NULL));
	//int randi = left + rand() % (right - left + 1);
	//swap(&arr[left], &arr[randi]);

	//三路取中
	int midi = threewaymid(arr, left, right);

	//左【left, keyi - 1】   右【keyi+1,right】
	int keyi = _QuickSort3(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr,keyi+1,right);
}

//快速排序非递归版本
void QuickSortNoare(int* arr, int left, int right)
{
	ST s;
	STInit(&s);

	STPush(&s, right);
	STPush(&s, left);

	while (!STEmpty(&s))
	{
		int begin = STTop(&s);
		STPop(&s);

		int end = STTop(&s);
		STPop(&s);

		//begin keyi end
		
		//自己实现一遍
		//左【begin,keyi-1】  右【keyi+1,end】
	/*	int keyi = begin;
		int prev = begin; int cur = prev + 1;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi] && ++prev != cur)
			{
				swap(&arr[cur], &arr[prev]);
			}
			cur++;
		}
		swap(&arr[prev], &arr[keyi]);
		keyi = prev;*/

		//直接调用
		int keyi = _QuickSort3(arr, begin, end);

		//右
		if (keyi + 1 < end)
		{
			STPush(&s, end);
			STPush(&s, keyi + 1);
		}

		//左
		if (begin < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, begin);
		}
	}
	STDestory(&s);
}




//快速排序进阶
//三路划分实现快速排序(结合随机数法或三位取中)--应对大量重复数据和有序的情况

//三数取中
int threewaymid(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[right])
	{
		swap(&arr[left], &arr[right]);
	}
	if (arr[mid] > arr[right])
	{
		swap(&arr[mid], &arr[right]);
	}
	if (arr[mid] < arr[left])
	{
		swap(&arr[mid], &arr[left]);
	}
	return mid;
}

void QuickSortMore(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	////随机数取法
	//srand((unsigned int)time(NULL));
	//int randi = left + rand() % (right - left + 1);
	//swap(&arr[left], &arr[randi]);

	//三数取中
	int midi = threewaymid(arr, left, right);
	swap(&arr[midi], &arr[left]);


	//三路划分
	int key = arr[left];
	int cur = left + 1;
	int begin = left;
	int end = right;

	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			swap(&arr[left], &arr[cur]);
			left++;
			cur++;
		}
		else if (arr[cur] > key)
		{
			swap(&arr[right], &arr[cur]);
			right--;
		}
		else {
			cur++;
		}
	}
		//三路划分【begin,left-1】【left,right】【right+1,end】
		QuickSortMore(arr, begin, left - 1);
		QuickSortMore(arr, right + 1, end);
}


////自省排序
////#include"introsort.h"
//
//void Swap(int* x, int* y)
//{
//	int tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//void AdjustDown(int* a, int n, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		// 选出左右孩⼦中⼤的那⼀个
//		if (child + 1 < n && a[child + 1] > a[child])
//		{
//			++child;
//		}
//		if (a[child] > a[parent])
//		{
//			Swap(&a[child], &a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//void HeapSort(int* a, int n)
//{
//	// 建堆 -- 向下调整建堆 -- O(N)
//	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
//	{
//		AdjustDown(a, n, i);
//	}
//	// 需要自己先实现 -- O(N*logN)
//
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&a[end], &a[0]);
//		AdjustDown(a, end, 0);
//		--end;
//	}
//}
//void InsertSort(int* a, int n)
//{
//	for (int i = 1; i < n; i++)
//	{
//		int end = i - 1;
//		int tmp = a[i];
//		// 将tmp插⼊到[0,end]区间中，保持有序
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//				--end;
//			}
//			else
//			{
//				break;
//			}
//		}
//		a[end + 1] = tmp;
//	}
//}
//
//// 三值取中函数
//int MedianOfThree(int* arr, int left, int right)
//{
//	int mid = left + (right - left) / 2;
//
//	// 比较并交换，确保 arr[left] <= arr[mid] <= arr[right]
//	if (arr[left] > arr[mid])
//		Swap(&arr[left], &arr[mid]);
//	if (arr[left] > arr[right])
//		Swap(&arr[left], &arr[right]);
//	if (arr[mid] > arr[right])
//		Swap(&arr[mid], &arr[right]);
//
//	// 使用中间值作为基准值，并将其移到 left 位置
//	Swap(&arr[left], &arr[mid]);
//
//	return arr[left]; // 返回基准值
//}
//
//void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
//{
//	if (left >= right)
//		return;
//
//	// 数组⻓度小于16的小数组，换为插入排序，简单递归次数
//	if (right - left + 1 < 16)
//	{
//		InsertSort(a + left, right - left + 1);
//		return;
//	}
//	// 当深度超过2*logN时改用堆排序
//
//	if (depth > defaultDepth)
//	{
//		HeapSort(a + left, right - left + 1);
//		return;
//	}
//	depth++;
//	int begin = left;
//	int end = right;
//	// 随机选key
//	int randi = left + (rand() % (right - left + 1));
//	Swap(&a[left], &a[randi]);
//	//也可以三值取中选key
//	//int key = MedianOfThree(arr, left, right);
//	int prev = left;
//	int cur = prev + 1;
//	int keyi = left;
//	while (cur <= right)
//	{
//		if (a[cur] < a[keyi] && ++prev != cur)
//		{
//			Swap(&a[prev], &a[cur]);
//		}
//		++cur;
//	}
//	Swap(&a[prev], &a[keyi]);
//	keyi = prev;
//	// [begin, keyi-1] keyi [keyi+1, end]
//	IntroSort(a, begin, keyi - 1, depth, defaultDepth);
//	IntroSort(a, keyi + 1, end, depth, defaultDepth);
//}
//void QuickSort(int* a, int left, int right)
//{
//	int depth = 0;
//	int logn = 0;
//	int N = right - left + 1;
//	for (int i = 1; i < N; i *= 2)
//	{
//		logn++;
//	}
//
//	// introspective sort -- ⾃省排序
//	IntroSort(a, left, right, depth, logn * 2);
//
//}
//int* sortArray(int* nums, int numsSize, int* returnSize)
//{
//	srand(time(0));
//	QuickSort(nums, 0, numsSize - 1);
//
//	*returnSize = numsSize;
//	return nums;
//}




void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	
	//分解
	//[left,mid][mid+1,right]
	int mid = left + (right-left) / 2;  
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid+1, right, tmp);

	//合并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;//一定是left而不是0，不然会受到影响

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else {
			tmp[index++] = arr[begin2++];
		}
	}

	//有一个结束了，另外一个还没结束
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	//把数据拷贝回去
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

//归并排序--主函数里面不递归，所以可以先不传left和right
void MergeSort(int* arr, int n)
{
	//开辟一个新数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}



//非递归实现归并排序
void MergeSortNore(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i,end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[index++] = arr[begin1++];
				}
				else {
					tmp[index++] = arr[begin2++];
				}
			}
			//有一个结束了，另外一个还没结束

			while (begin1 <= end1)
			{
				tmp[index++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = arr[begin2++];
			}

			//把数据拷贝回去
			memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
}


//非比较排序--计数排序
void CountSort(int* arr, int n)
{
	//找最大最小值确定范围
	int min = arr[0]; int max = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}

	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(-1);
	}

	//对count初始化，可以用memset也可以前面申请空间的时候使用calloc
	memset(count, 0, sizeof(int) * range);

	//统计次数，映射，下标为arr[i]-min
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}

	//排序
	int index = 0;
	//用range就可以了
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;//这里需要用i+min
		}
	}
}
